home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / utils.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  9KB  |  352 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)utils.c    5.3 (Berkeley) 3/3/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include "btree.h"
  46. #include "utils.h"
  47.  
  48. /*
  49.  *  _BT_BUILDRET -- Build return key/data pair as a result of search or scan.
  50.  *
  51.  *    This routine manages the statically allocated buffers in which we
  52.  *    return data to the user.
  53.  *
  54.  *    Parameters:
  55.  *        t -- btree from which to return datum
  56.  *        d -- DATUM to be returned to the user.
  57.  *        data -- data argument supplied by user for return
  58.  *        key -- key argument supplied by user for return
  59.  *
  60.  *    Returns:
  61.  *        RET_SUCCESS, RET_ERROR.
  62.  *
  63.  *    Side Effects:
  64.  *        May free and reallocate static buffers, if the data
  65.  *        we want to return is bigger than the space we have to
  66.  *        do so.
  67.  */
  68.  
  69. int
  70. _bt_buildret(t, d, data, key)
  71.     BTREE_P t;
  72.     DATUM *d;
  73.     DBT *data;
  74.     DBT *key;
  75. {
  76.     static int _data_s = 0;
  77.     static int _key_s = 0;
  78.     static char *_data = (char *) NULL;
  79.     static char *_key = (char *) NULL;
  80.     pgno_t chain;
  81.  
  82.     if (d->d_flags & D_BIGKEY) {
  83.         if (_key != (char *) NULL)
  84.             (void) free(_key);
  85.         (void) bcopy((char *) &(d->d_bytes[0]),
  86.                        (char *) &chain,
  87.                        sizeof(chain));
  88.         if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR)
  89.             return (RET_ERROR);
  90.         key->data = (u_char *)_key;
  91.         key->size = _key_s;
  92.     } else {
  93.         /* need more space for key? */
  94.         if (d->d_ksize > _key_s) {
  95.             if (_key != (char *) NULL)
  96.                 (void) free (_key);
  97.             if ((_key = (char *) malloc((unsigned) d->d_ksize))
  98.                 == (char *) NULL)
  99.                 return (RET_ERROR);
  100.             _key_s = d->d_ksize;
  101.         }
  102.  
  103.         key->data = (u_char *)_key;
  104.         if ((key->size = d->d_ksize) > 0)
  105.             (void) bcopy(&(d->d_bytes[0]),
  106.                      _key,
  107.                      (int) d->d_ksize);
  108.     }
  109.  
  110.     if (d->d_flags & D_BIGDATA) {
  111.         if (_data != (char *) NULL)
  112.             (void) free(_data);
  113.         (void) bcopy(&(d->d_bytes[d->d_ksize]),
  114.                        (char *) &chain,
  115.                        sizeof(chain));
  116.         if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR)
  117.             return (RET_ERROR);
  118.         data->data = (u_char *)_data;
  119.         data->size = _data_s;
  120.     } else {
  121.         /* need more space for data? */
  122.         if (d->d_dsize > _data_s) {
  123.             if (_data != (char *) NULL)
  124.                 (void) free (_data);
  125.             if ((_data = (char *) malloc((unsigned) d->d_dsize))
  126.                 == (char *) NULL)
  127.                 return (RET_ERROR);
  128.             _data_s = d->d_dsize;
  129.         }
  130.  
  131.         data->data = (u_char *)_data;
  132.  
  133.         if ((data->size = d->d_dsize) > 0)
  134.             (void) bcopy(&(d->d_bytes[d->d_ksize]),
  135.                       _data,
  136.                       (size_t) (d->d_dsize));
  137.     }
  138.  
  139.     return (RET_SUCCESS);
  140. }
  141.  
  142. /*
  143.  *  _BT_CMP -- Compare a key to a given item on the current page.
  144.  *
  145.  *    This routine is a wrapper for the user's comparison function.
  146.  *
  147.  *    Parameters:
  148.  *        t -- tree in which to do comparison
  149.  *        p -- pointer to one argument for the comparison function
  150.  *        n -- index of item to supply second arg to comparison function
  151.  *
  152.  *    Returns:
  153.  *        < 0 if p is < item at n
  154.  *        = 0 if p is = item at n
  155.  *        > 0 if p is > item at n
  156.  */
  157.  
  158. int
  159. _bt_cmp(t, p, n)
  160.     BTREE_P t;
  161.     char *p;
  162.     index_t n;
  163. {
  164.     BTHEADER *h;
  165.     IDATUM *id;
  166.     DATUM *d;
  167.     char *arg;
  168.     int ignore;
  169.     int free_arg;
  170.     pgno_t chain;
  171.     int r;
  172.  
  173.     h = t->bt_curpage;
  174.  
  175.     /*
  176.      *  The left-most key at any level of the tree on internal pages
  177.      *  is guaranteed (artificially, by the code here) to be less than
  178.      *  any user key.  This saves us from having to update the leftmost
  179.      *  key when the user inserts a new key in the tree smaller than
  180.      *  anything we've seen yet.
  181.      */
  182.  
  183.     if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0)
  184.         return (1);
  185.  
  186.     if (h->h_flags & F_LEAF) {
  187.         d = (DATUM *) GETDATUM(h,n);
  188.         if (d->d_flags & D_BIGKEY) {
  189.             free_arg = TRUE;
  190.             bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain));
  191.             if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
  192.                 return (RET_ERROR);
  193.         } else {
  194.             free_arg = FALSE;
  195.             arg = &(d->d_bytes[0]);
  196.         }
  197.     } else {
  198.         id = (IDATUM *) GETDATUM(h,n);
  199.         if (id->i_flags & D_BIGKEY) {
  200.             free_arg = TRUE;
  201.             bcopy(&(id->i_bytes[0]),
  202.                   (char *) &chain,
  203.                   sizeof(chain));
  204.             if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
  205.                 return (RET_ERROR);
  206.         } else {
  207.             free_arg = FALSE;
  208.             arg = &(id->i_bytes[0]);
  209.         }
  210.     }
  211.     r = (*(t->bt_compare))(p, arg);
  212.  
  213.     if (free_arg)
  214.         (void) free(arg);
  215.  
  216.     return (r);
  217. }
  218.  
  219. /*
  220.  *  _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack.
  221.  *
  222.  *    When we descend the tree, we keep track of parent pages in order
  223.  *    to handle splits on insertions.
  224.  *
  225.  *    Parameters:
  226.  *        t -- tree for which to push parent
  227.  *        pgno -- page number to push (_bt_push only)
  228.  *
  229.  *    Returns:
  230.  *        RET_SUCCESS, RET_ERROR.
  231.  */
  232.  
  233. int
  234. _bt_push(t, pgno)
  235.     BTREE_P t;
  236.     pgno_t pgno;
  237. {
  238.     BTSTACK *new;
  239.  
  240.     if ((new = (BTSTACK *) malloc((unsigned) sizeof(BTSTACK)))
  241.         ==  (BTSTACK *) NULL)
  242.         return (RET_ERROR);
  243.     new->bts_pgno = pgno;
  244.     new->bts_next = t->bt_stack;
  245.     t->bt_stack = new;
  246.  
  247.     return (RET_SUCCESS);
  248. }
  249.  
  250. pgno_t
  251. _bt_pop(t)
  252.     BTREE_P t;
  253. {
  254.     BTSTACK *s;
  255.     pgno_t p = P_NONE;
  256.  
  257.     if ((s = t->bt_stack) != (BTSTACK *) NULL) {
  258.         p = s->bts_pgno;
  259.         t->bt_stack = s->bts_next;
  260.         (void) free ((char *) s);
  261.     }
  262.     return (p);
  263. }
  264.  
  265. #ifdef DEBUG
  266. void
  267. _btdump(tree)
  268.     BTREE tree;
  269. {
  270.     BTREE_P t = (BTREE_P) tree;
  271.     DATUM *d;
  272.     IDATUM *id;
  273.     BTHEADER *h;
  274.     pgno_t npages;
  275.     pgno_t i;
  276.     index_t cur, top;
  277.  
  278.     npages = t->bt_npages;
  279.     (void) printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx",
  280.         t->bt_fname, t->bt_s.bt_d.d_fd,
  281.         t->bt_psize, t->bt_curpage);
  282.     (void) printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare);
  283.     if (t->bt_flags & BTF_SEQINIT)
  284.         (void) printf("BTF_SEQINIT");
  285.     (void) printf(")\n");
  286.  
  287.     for (i = P_ROOT; i <= npages; i++) {
  288.         if (_bt_getpage(t, i) == RET_ERROR)
  289.             _punt();
  290.         h = t->bt_curpage;
  291.         top = NEXTINDEX(h);
  292.         (void) printf("    page %d:\n", i);
  293.         (void) printf("\tpgno %d prev %d next %d\n",
  294.             h->h_pgno, h->h_prevpg, h->h_nextpg);
  295.         (void) printf("\tlower %d upper %d nextind %d flags (",
  296.             h->h_lower, h->h_upper, top);
  297.         if (h->h_flags & F_LEAF)
  298.             (void) printf("F_LEAF");
  299.         else
  300.             (void) printf("<internal>");
  301.         if (h->h_flags & F_DIRTY)
  302.             (void) printf("|F_DIRTY");
  303.         if (h->h_flags & F_PRESERVE)
  304.             (void) printf("|F_PRESERVE");
  305.         if (h->h_flags & F_CONT) {
  306.             (void) printf("|F_CONT)");
  307.             if (h->h_prevpg == P_NONE) {
  308.                 size_t longsz;
  309.                 (void) bcopy((char *) &(h->h_linp[0]),
  310.                           (char *) &longsz,
  311.                           sizeof(longsz));
  312.                 printf("\n\t\t(chain start, data length %ld)",
  313.                     longsz);
  314.             }
  315.             printf("\n");
  316.             continue;
  317.         }
  318.         (void) printf(")\n");
  319.         for (cur = 0; cur < top; cur++) {
  320.             (void) printf("\t  [%d] off %d ", cur, h->h_linp[cur]);
  321.             if (h->h_flags & F_LEAF) {
  322.                 d = (DATUM *) GETDATUM(h,cur);
  323.                 (void) printf("ksize %d", d->d_ksize);
  324.                 if (d->d_flags & D_BIGKEY)
  325.                     (void) printf(" (indirect)");
  326.                 (void) printf("; dsize %d", d->d_dsize);
  327.                 if (d->d_flags & D_BIGDATA)
  328.                     (void) printf(" (indirect)");
  329.             } else {
  330.                 id = (IDATUM *) GETDATUM(h,cur);
  331.                 (void) printf("size %d pgno %d",
  332.                     id->i_size, id->i_pgno);
  333.                 if (id->i_flags & D_BIGKEY)
  334.                     (void) printf(" (indirect)");
  335.             }
  336.             (void) printf("\n");
  337.         }
  338.         (void) printf("\n");
  339.     }
  340. }
  341. #endif /* DEBUG */
  342.  
  343. #ifdef DEBUG
  344. _punt()
  345. {
  346.     int pid;
  347.  
  348.     pid = getpid();
  349.     (void) kill(pid, SIGILL);
  350. }
  351. #endif /* DEBUG */
  352.